Users are increasingly performing tasks using remote computing resources, which may be offered through a shared-resource environment. This has many advantages, as users do not have to purchase and maintain dedicated hardware and software, and instead can pay for only those resources that are utilized at any given time, where those resources typically will be managed by a resource provider. Users can perform tasks such as storing data or executing applications using various types of resources offered by the resource provider. In many cases the data to be processed will be secured using one or more cryptographic keys or other such security credentials. In order to ensure that these keys are not obtained by unauthorized parties, the keys are often stored in devices such as hardware security modules (HSMs). In conventional approaches, a dedicated HSM device is allocated to a customer over a period of time. Such an approach can be relatively expensive for the customer, and wasteful for the resource provider, since the customer is charged for the time that the HSM device is allocated to the customer even though the HSM device will likely be sitting idle the vast majority of the time and thus drastically underutilized.